/*
 * Created on Jun 26, 2011
 *
 * Spectro-Edit is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Spectro-Edit is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>. 
 */
package org.naivecode.audio;

import java.util.ArrayList;
import java.util.List;

public class FeatureSpace {
	private static final float UNRELIABLE = Float.MAX_VALUE;
	private final List<Extremum> extremums = new ArrayList<Extremum>();
	private LineDetectorContext detectorContext = new LineDetectorContext();
	private int numberOfFrames;
	private final float[] values;

	public FeatureSpace(int frameSize) {
		values = new float[frameSize];
	}

	public void appendFrame(float[] frequencies, int offset, int length) {
		System.arraycopy(frequencies, offset, values, 0, length);
		smoothen(values, 3);
		extremums.clear();
		findExtremums(values, extremums, length);
		simplify(extremums, 3);
		matchExtremums(detectorContext, extremums, numberOfFrames);
		numberOfFrames++;
	}

	public int getNumberOfFrames() {
		return numberOfFrames;
	}

	/**
	 * Simple sliding average smoothing
	 */
	private void smoothen(float[] frequencies, int halfWinodow) {
		for (int i = halfWinodow; i < frequencies.length - halfWinodow; i++) {
			// calculate window average
			float avg = 0;
			for (int iw = -halfWinodow; iw < halfWinodow; iw++) {
				avg += frequencies[i + iw];
			}
			frequencies[i] = avg / (halfWinodow * 2);
		}
		float avgl = 0;
		float avgr = 0;
		for (int i = 0; i < halfWinodow; i++) {
			final int ii = frequencies.length - i - 1;
			avgl += frequencies[i];
			avgr += frequencies[ii];
			frequencies[i] = avgl / (i + 1);
			frequencies[ii] = avgr / (i + 1);
		}
	}

	/* package */void findExtremums(float[] values, List<Extremum> ext,
			float tolerance) {
		float delta = 0;
		float prevDelta = 0;
		float prevPlateauPosition = -1;
		for (int i = 1; i < values.length; i++) {
			delta = slope(values, i, 64, tolerance);
			if (delta == UNRELIABLE) {
				// slope is unreliable
				continue;
			}

			if (Math.signum(prevDelta) != Math.signum(delta)) {
				// reached candidate point
				if (delta == 0) {
					if (prevPlateauPosition < 0) {
						prevPlateauPosition = i - 1;
					}
				} else {
					// end of plateau or valley ?
					if (prevPlateauPosition >= 0) {
						ext.add(new Extremum(i - 1,
								i - 1 - prevPlateauPosition, values[i - 1]));
					} else {
						// previous location was extremum
						ext.add(new Extremum(i - 1, values[i - 1]));
					}
					prevPlateauPosition = -1;
					prevDelta = delta;
				}
			}
		}
	}

	private float slope(float[] data, int pos, int window, float tolerance) {
		final int maxWnd = Math.min(pos + window, data.length) - pos;
		int plus = 0;
		int minus = 0;
		float maxDelta = 0;
		for (int w = 1; w < maxWnd; w *= 2) {
			final float delta = data[pos] - data[pos + w];
			maxDelta += Math.abs(delta);
			if (delta > 0) {
				plus++;
			} else {
				minus++;
			}
		}
		if (maxDelta / (plus + minus) < tolerance) {
			return 0;
		}
		if (Math.abs(plus - minus) <= ((plus + minus) / 2)) {
			return UNRELIABLE;
		}
		return plus - minus;
	}

	/* package */void simplify(List<Extremum> ext, float window) {
		// sparse array can contain null entries
		final Extremum[] sparceExtrema = ext.toArray(new Extremum[ext.size()]);
		boolean keepOn = true;
		while (keepOn) {
			keepOn = false;
			int ii = nextNonzeroIndex(sparceExtrema, -1);
			for (int i = nextNonzeroIndex(sparceExtrema, ii); i < sparceExtrema.length; i = nextNonzeroIndex(
					sparceExtrema, ii)) {
				if (i < 0) {
					break;
				}
				final Extremum ie = sparceExtrema[i];
				final Extremum iie = sparceExtrema[ii];

				float leftBound = ie.frequency - ie.frequencySpread;
				if (Math.abs(iie.frequency - leftBound) < window) {
					final float weightedMagnitude = (iie.magnitude
							* iie.frequencySpread + ie.magnitude
							* ie.frequencySpread)
							/ (iie.frequencySpread + ie.frequencySpread);

					sparceExtrema[ii] = new Extremum(ie.frequency,
							iie.frequencySpread + ie.frequencySpread,
							weightedMagnitude);
					sparceExtrema[i] = null;
					ii = nextNonzeroIndex(sparceExtrema, i);
					keepOn = true;
				} else {
					ii = i;
				}
			}
		}
		ext.clear();
		for (Extremum e : sparceExtrema) {
			if (e != null) {
				ext.add(e);
			}
		}
	}

	private int nextNonzeroIndex(Extremum[] ext, int currentIndex) {
		for (int i = currentIndex + 1; i < ext.length; i++) {
			if (ext[i] != null) {
				return i;
			}
		}
		return -1;
	}

	private void matchExtremums(LineDetectorContext ldc, List<Extremum> next,
			float time) {

		final List<LinearSequence> closedLines = new ArrayList<LinearSequence>(
				ldc.getActiveLines());
		final List<Extremum> newLines = new ArrayList<Extremum>(next);

		for (LinearSequence line : ldc.getActiveLines()) {
			for (Extremum e : next) {
				if (line.fits(e)) {
					closedLines.remove(line);
					newLines.remove(e);
					line.append(e);
				}
			}
		}
		for (Extremum e : newLines) {
			ldc.startLine(time).append(e);
		}
		for (LinearSequence ls : closedLines) {
			ldc.terminateLine(ls);
		}
	}

}
